package Offer.offer2016;
/**
 * ���������� �� ���������� ������Ϊ�� ����С�ڸ��ڵ㣬������Ϊ�ջ��ߴ��ڸ��ڵ�
 * @author ���Ŀ�
 *
 */
public class Test24 
{

	public static void main(String[] args) 
	{
		int[] array={7,8};
        System.out.println(IsBST.isBST(array));
	}
    public static boolean isBST(int[] array)
    {
    	if(array==null||array.length==0)
    		return false;
    	return isBST(array,0,array.length-1);
    }
    public static boolean isBST(int[] array,int start,int end)
    {
    	int i =start;
    	if(start<end)
    	{
    		for(;i<=end;i++)
        	{
        		if(array[i]>array[end])
        			break;
        	}
        	for(int j=i;j<end;j++)
        	{
        		if(array[j]<array[end])
        			return false;
        	}
        	return isBST(array,start,i-1)&&isBST(array,i,end-1);
    	}
    	return true;
    }
}
class IsBST{
	public static boolean isBST(int []arr){
		if(arr == null || arr.length == 0){
			return false;
		}
		return isBST(arr,0,arr.length - 1);
	}
	
	public static boolean isBST(int []arr,int start,int end){
		if(start == end){
			return true;
		}
		int rightIndex = 0;
		for(int i = start ; i < end ; i++){
			if(arr[i] > arr[end]){
				rightIndex = i;
				break;
			}
		}
		if (rightIndex < end) {
			for(int i = rightIndex; i < end; i++){
				if(arr[i] < arr[end]){
					return false;
				}
			}
		}
		return isBST(arr, start, rightIndex - 1) && isBST(arr, rightIndex, end - 1);
	}
	
}